/*
 * @lc app=leetcode.cn id=338 lang=csharp
 *
 * [338] 比特位计数
 */

// @lc code=start
public class Solution {
    public int[] CountBits(int n) {
        int[] ans = new int[n+1];
        for(int i = 0; i <= n; ++i)
        {
            ans[i] = HammingWeight(i);
        }
        return ans;
        
        
        /*
        0000 0000 0 0
        0000 0001 1 1
        0000 0010 1 2
        0000 0011 2 3
        0000 0100 1 4
        0000 0101 2 5
        0000 0110 2 6
        0000 0111 3 7
        0000 1000 1 8
        
        */
    }
    
    public int HammingWeight(int i) {
        i = (i & 0x55555555) + ((i >> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
        i = (i & 0x0f0f0f0f) + ((i >> 4) & 0x0f0f0f0f);
        i = (i * (0x01010101) >> 24);
        return i;
    }
}
// @lc code=end

